package _interview150;

/**
 * 97. 交错字符串
 */
public class No97 {
    private String s1, s2, s3;
    private Boolean[][][] cache;

    public boolean isInterleave(String s1, String s2, String s3) {
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
        cache = new Boolean[100][100][200];
        return dfs(s1.length() - 1, s2.length() - 1, s3.length() - 1);
    }

    private boolean dfs(int i, int j, int k) {
        if (k < 0) return i < 0 && j < 0;
        else if (i < 0) return j == k && s2.substring(0, j + 1).equals(s3.substring(0, k + 1));
        else if (j < 0) return i == k && s1.substring(0, i + 1).equals(s3.substring(0, k + 1));
        else if (cache[i][j][k] != null) return cache[i][j][k];
        else if (s1.charAt(i) != s3.charAt(k) && s2.charAt(j) != s3.charAt(k)) return cache[i][j][k] = false;
        else if (s1.charAt(i) != s3.charAt(k)) return cache[i][j][k] = dfs(i, j - 1, k - 1);
        else if (s2.charAt(j) != s3.charAt(k)) return cache[i][j][k] = dfs(i - 1, j, k - 1);
        else return cache[i][j][k] = dfs(i, j - 1, k - 1) || dfs(i - 1, j, k - 1);
    }
}
